//编写一个函数，检查输入的链表是否是回文的。 
//
// 
//
// 示例 1： 
//
// 输入： 1->2
//输出： false 
// 
//
// 示例 2： 
//
// 输入： 1->2->2->1
//输出： true 
// 
//
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表

package leetcode.editor.cn;

import java.util.ArrayList;

public class PalindromeLinkedListLcci {
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedListLcci().new Solution();
        ListNode node = ListNodeUtil.constructList(new int[]{1, 2});
        boolean palindrome = solution.isPalindrome(node);
        System.out.println(palindrome);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            list.add(p.val);
            p = p.next;
        }

        p = head;
        ListNode prev = null;
        ListNode tmp = null;
        while (p != null) {
            tmp = p.next;
            p.next = prev;

            prev = p;
            p = tmp;
        }

        p = prev;
        int counter = 0;
        while (p != null) {
            boolean b = p.val == list.get(counter);
            if (b) {
                p = p.next;
                counter++;
            } else {
                return false;
            }
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}